// 279.完全平方数
package LeetcodeHot100;

public class Solution279 {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        for (int i = 0; i < n + 1; i++) {
            if (judge(i) == true) {
                dp[i] = 1;
            } else {
                int min = Integer.MAX_VALUE;
                for (int j = 1; j * j < i; j++) {
                    min = Math.min(min, dp[i - j * j] + 1);
                }
                dp[i] = min;
            }
        }
        return dp[n];
    }

    public boolean judge(int n) {
        for (int i = 1; i <= Math.sqrt(n + 1); i++) {
            if (i * i == n)
                return true;
        }
        return false;
    }
}
